package libsvm;
import java.util.*;

public class RelationKernel
{
  static final double DEFAULT_LAMBDA = 0.75;
  static final boolean DEFAULT_CACHE = true; 
  static final boolean DEFAULT_NORM = true; 

  // gap penalty
  double m_lambda;
  // true if cached self kernels
  boolean m_bCache;
  // true if normalized kernels
  boolean m_bNorm;
	
  protected HashMap m_mapStoK;

  public RelationKernel(double lambda, boolean bCache, boolean bNorm)
  {
    m_lambda = lambda;
    m_bCache = bCache;
    m_bNorm = bNorm;

    m_mapStoK = new HashMap();
  }

  public RelationKernel() 
  {
    m_lambda = DEFAULT_LAMBDA;
    m_bCache = DEFAULT_CACHE;
    m_bNorm = DEFAULT_NORM;

    m_mapStoK = new HashMap();
  }


  /**
     Computes the normalized string kernel between two strings.
     @param s1 string 1
     @param s2 string 2
     @return normalized value, with 1 for exact match.
  */
  public double normKernel(String[][] s1, String[][] s2) 
  {
    double k1 = selfKernel(s1);
    double k2 = selfKernel(s2);
    
    double k = kernel(s1, s2);

    // normalize
    return k / Math.sqrt (k1 * k2);				
  }
  
  
  public double selfKernel(String[][] s)
  {
    if (m_bCache) {
      // get string representation of relation instance
      String strText = "";
      for (int i = 0; i < s.length; i++)
	strText += s[i][0] + " ";
      // get cached value
      Double dblk = (Double) m_mapStoK.get(strText);
      if (dblk == null) {
	double k = kernel(s, s);
	m_mapStoK.put(strText, new Double(k));
	return k;
      }
      return dblk.doubleValue();
    }

    return kernel(s, s);
  }
  

  public double kernel(String[][] s1, String[][] s2)
  {
    if (s1.length != s2.length)
      return 0;

    int n = s1.length;
    if (n > 10)
      return 0;

    double rK = 1;
    for (int i = 0; i < n; i++)
      rK = rK * common(s1[i], s2[i]);

    return rK;
  }


  protected double stringKernel(String[][] s, String[][] t, int n, double lambda)
  {
    double r = 0.0;
    int slen = s.length;
    int tlen = t.length;
    
    double[][] K = new double[n + 1][slen * tlen];
    
    for (int j = 0; j < slen; j++)
      for (int k = 0; k < tlen; k++)
	K[0][k * slen + j] = 1;
    
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < slen - 1; j++) {
	double sum = 0.0;
	for (int k = 0; k < tlen - 1; k++) {
	  sum = lambda * (sum + 
			  lambda * common(t[k], s[j])  * K[i][k * slen + j]);
	  K[i + 1][(k + 1) * slen + j + 1] = 
	    lambda * K[i + 1][(k + 1) * slen  + j] + sum;
	}
      }
    }

    for (int j = 0; j < slen; j++)
      for (int k = 0; k < tlen; k++)
	r = r + lambda * lambda * common(t[k], s[j]) * K[n - 1][k * slen + j];
    
    //    double powl = Math.pow(lambda, n);
    //    return r / (powl * powl);
    return r;
  }


  protected double sKernel(String[][] s, String[][] t, int n, double lambda)
  {
    double r = 0.0;
    int slen = s.length;
    int tlen = t.length;
    
    double[][] K = new double[n + 1][(slen + 1) * (tlen + 1)];
    
    for (int j = 0; j < slen + 1; j++)
      for (int k = 0; k < tlen + 1; k++)
	K[0][k * (slen + 1) + j] = 1;
    
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < slen; j++) {
	double sum = 0.0;
	for (int k = 0; k < tlen; k++) {
	  sum = lambda * (sum + 
			  lambda * common(t[k], s[j]) * K[i][k * (slen + 1) + j]);
	  K[i + 1][(k + 1) * (slen + 1) + j + 1] = 
	    lambda * K[i + 1][(k + 1) * (slen + 1) + j] + sum;
	}
      }
    }

    //    double powl = Math.pow(lambda, n);
    //    return K[n][tlen * (slen + 1) + slen] / (powl * powl);
    return K[n][tlen * (slen + 1) + slen];
  }


  protected int common(String[] s, String[] t)
  {
    assert s.length == t.length;
    int nCount = 0;
    for (int i = 0; i < s.length; i++)
      if (s[i] != null && s[i] == t[i])
	nCount++;

    return nCount;
  }


  protected void normalize(String[][] s1, String[][] s2)
  {
    for (int i = 0; i < s1.length; i++)
      for (int j = 0; j < s2.length; j++)
	if (s1[i][0].equals(s2[j][0]))
	  s2[j][0] = s1[i][0];
  }


  protected String[][] mirror(String[][] s)
  {
    String[][] t = new String[s.length][];
    for (int i = 0; i < s.length; i++)
      t[s.length - i - 1] = s[i];

    return t;
  }


  public static void main (String[] args)
  {
    String per = "per";
    String gpe = "gpe";
    String[][] s1 = {{"<p1>", per}, 
		     {"c", null}, {"b", "B", null}, {"c", null},
		     {"<p2>", gpe}};
    String[][] s2 = {{"<p3>", per}, 
		     {"c", null}, {"b", "B", null}, {"c", null},
		     {"<p4>", gpe}};

    RelationKernel rk = new RelationKernel();
    System.out.println(rk.kernel(s1, s2));
  }

}

